345 artigos
Este artigo prova que a soma dos tamanhos do núcleo e do diadema de um grafo é no máximo $2\alpha(G)2\alpha(G) + kk$ é o número de ciclos ímpares distintos em vértices), confirmando outra conjectura recente e estabelecendo uma cadeia de desigualdades entre esses conjuntos.
Este artigo demonstra que a conjectura sobre o grau mínimo de grafos --fator-críticos minimais, que postula que tal grau está entre e , é válida para grafos -planares, resolvendo assim a questão para o caso específico de grafos planares.
Este artigo investiga a seleção de partições de dois blocos ótimas para acelerar a convergência de cadeias de Markov finitas, estabelecendo conexões teóricas entre divergência de Kullback-Leibler e distância de Frobenius com a cadeia projetada induzida, e propondo algoritmos de aproximação eficientes para resolver o problema de otimização combinária resultante.
O artigo demonstra que, para um conjunto de pontos no plano com diâmetro no máximo 1, a razão entre o número de pares vizinhos (distância ) e o número de pares antípodas (distância ) é da ordem de , superando o limite anterior de e aproximando-se da cota assintótica conjecturada.
O artigo confirma duas conjecturas de Huang, Huang e Cioabă ao demonstrar que o gráfico de Johnson de bandeira completa possui um mesmo gap espectral que o seu quociente de Schreier, estabelecendo assim um fenômeno do tipo Aldous para essa estrutura.
Este artigo determina a estrutura completa dos valores nim para jogos de subtração aditiva no regime quadrático primitivo, fornecendo uma prova definitiva para uma fórmula fechada clássica envolvendo expressões de Brakets do tipo Beatty que caracteriza as posições P e demonstrando que cada sequência de valores nim reside em um deslocamento linear dessas posições.
Este artigo estabelece um novo limite inferior para o número de beijos em 19 dimensões, provando que ele é pelo menos 11.948, o que representa um aumento de 256 sobre o limite anterior de Cohn e Li, por meio de uma construção que combina o método de sinal ímpar com um código binário não linear explícito derivado do código de Golay estendido.
Este artigo estabelece a existência e unicidade de uma solução para o fluxo de Ricci em grafos finitos com curvatura prescrita, demonstrando que, para grafos com circunferência de pelo menos 6, o fluxo converge exponencialmente para pesos de curvatura constante se e somente se uma condição de densidade de arestas for satisfeita, respondendo afirmativamente à Questão 2 de Chow e Luo sobre a analogia com o fluxo de Ricci combinatorial em 2D.
O artigo estabelece limites assintóticos precisos para os números de Ramsey relacionados ao número de Hadwiger, demonstrando que, para duas cores, o valor cresce proporcionalmente a , e generaliza essa relação para cores com uma constante específica.
Este artigo desenvolve fórmulas explícitas e compactas para o polinômio M de diversos produtos de grafos (como cartesiano, direto, forte, lexicográfico, diferença simétrica, disjunção e produto de Sierpiński), oferecendo uma descrição unificada de como as interações de graus dos vértices se propagam nessas construções e estendendo resultados existentes para índices topológicos baseados em graus.
Este artigo estabelece os índices de soma inversa indeg (ISI) máximos para árvores e grafos unícicos com diâmetro fixo, identificando as estruturas extremas que alcançam esses valores por meio de métodos de transformação de grafos.
Este artigo investiga os números anti-Ramsey para cópias fracas e fortes de posets, estabelecendo conexões com números extremos e determinando assintoticamente esses valores para posets em árvore e coroa.
Este artigo estabelece os primeiros teoremas do limite central para polítopos de rede aleatórios, analisando o comportamento assintótico e as flutuações normais do número de arestas e de triangulações unimodulares em polítopos de aresta simétrica gerados por grafos aleatórios de Erdős–Rényi em regime de alta dimensão.
O artigo demonstra que a família de todos os conjuntos com valor em uma função submodular simétrica de valor inteiro pode ser representada de forma polinomial e fornece um algoritmo eficiente para sua construção, generalizando resultados anteriores sobre funções de corte-rank em grafos e permitindo a resolução de problemas de cardinalidade prescrita em tempo polinomial para fixo.
O artigo demonstra que os coeficientes principais e penúltimos dos termos de erro do método NRS(2) aplicado a um polinômio cúbico são polinômios com coeficientes positivos em e , simplificando e estendendo resultados anteriores.
Este artigo demonstra que os fatores de palavras suaves são f-suaves e avança na conjectura de Sing sobre a complexidade das palavras f-suaves binárias, provando a fórmula assintótica para alfabetos pares, estabelecendo o limite inferior para qualquer alfabeto binário e melhorando o limite superior conhecido para alfabetos ímpares.
Este artigo introduz os conceitos generalizados de complexos simpliciais com vértices dispensáveis e escaláveis, estabelecendo suas equivalências com propriedades de esquelética inicial, caracterizando-os algebricamente por meio de ideais Alexander duais e demonstrando que, em casos específicos, tais propriedades são equivalentes à fraca conectividade.
Este artigo demonstra que, para suficientemente grande, as medidas de probabilidade uniformes sobre três famílias naturais de subgrafos de conexão do grafo completo satisfazem a propriedade de correlação negativa par a par, estendendo trabalhos anteriores e fornecendo a primeira verificação dessa propriedade para subgrafos conexos uniformes.
Este artigo estabelece uma nova conexão entre problemas extremos em digrafos e densidades de Turán uniformes em 3-grafos, fornecendo condições verificáveis para determinar esses valores, identificando classes específicas de 3-grafos e apresentando uma prova simplificada para a existência de 3-grafos com densidade de Turán uniforme igual a 1/27.
Este artigo apresenta novas perspectivas combinatórias sobre partições com partes pares distintas, estabelecendo conexões com partições assinadas e bicoloridas para obter identidades e fornecer provas bijetivas que respondem parcialmente a problemas propostos por Andrews-El Bachraoui e Kılıç-Kurşungöz.