341 artigos
Este artigo demonstra que a conjectura de Lovász é válida para grafos de Cayley densos moderadamente, provando que todo grafo de Cayley conexo grande com vértices e grau possui um ciclo hamiltoniano, utilizando um lema de regularidade aritmética eficiente especializado para grafos de Cayley em vez do lema de regularidade de Szemerédi.
Este artigo estuda a restrição do índice de profundidade aos emparelhamentos perfeitos, fornecendo uma descrição combinatória adicional e demonstrando que essa estatística é equidistribuída com a função de posto da ordem de Bruhat.
Este artigo fornece uma resposta positiva à Conjectura Alternativa das Árvores para a relação de menor de grafos, completando assim o estudo dessa conjectura para as três relações de grafos mais amplamente investigadas.
Este artigo apresenta uma versão do teorema da árvore matricial que relaciona o determinante de uma matriz a somas de pesos de arborescências em grafos direcionados, permitindo somas de colunas não nulas através da adição de um vértice raiz, e aplica esses resultados para provar um teorema de florestas matriciais e calcular a evolução temporal de sistemas com estados discretos.
O artigo introduz o conceito de "carton number" para analisar a complexidade computacional do número de scramble em grafos, demonstrando que scrambles não constituem certificados NP válidos devido a casos exponenciais, caracterizando famílias de grafos com aproximações eficientes, estabelecendo a tractabilidade fixa da versão disjunta e provando que a congestão de vértices limita o scramble number, o que resulta em novos limites para a largura de árvore de grafos de linha e para grafos planares.
Este artigo desenvolve ferramentas para o estudo quantitativo das árvores geradoras mínimas aleatórias (MST), abordando tanto o caso padrão de pesos independentes e identicamente distribuídos quanto generalizações para medidas produto com distribuições arbitrárias.
Este artigo investiga as propriedades dos grafos de Engel e co-Engel de grupos finitos, estabelecendo resultados sobre a distinção entre versões direcionadas e não direcionadas, a caracterização de subgrupos via vértices isolados, e o cálculo de invariantes espectrais e topológicos, culminando na classificação de grupos não-Engel cujos grafos possuem número de clique limitado e são toroidais ou projetivos.
Este artigo estabelece uma regra de Murnaghan-Nakayama para os caracteres irredutíveis da álgebra de Hecke ciclotômica, fornecendo uma via combinatória direta para sua tabela de caracteres e derivando novas fórmulas de bitraco e ortogonalidade, além de incluir uma implementação computacional em SageMath.
Este artigo investiga as propriedades do número cromático linear, um parâmetro relaxado da profundidade de árvore introduzido por Kun et al., e estabelece limites aprimorados para essa relação em várias classes de grafos.
Este artigo estabelece limites extremos precisos para os índices de irregularidade Sigma e Albertson em árvores com sequências de graus não decrescentes, demonstrando que as configurações extremas são frequentemente formadas por árvores tipo "caterpillar" e destacando o crescimento quadrático do índice Sigma em comparação ao crescimento linear do índice Albertson.
Este artigo estabelece uma separação exponencial entre os números cromáticos clássico e quântico para grafos de Hamming e generalizações de grafos de Hadamard, determinando os valores exatos do número cromático quântico em vários regimes através de novas abordagens de programação linear e método de traço, enquanto utiliza o método de padrões de interseção proibida para obter limites inferiores clássicos.
Este artigo investiga os números de Betti multigradados de mergulhos de Veronese de espaços projetivos, interpretando-os por meio da homologia de complexos simpliciais e aplicando a teoria de Morse discreta de Forman para estabelecer resultados de anulação e não anulação.
Este artigo caracteriza as famílias -intersectantes de conjuntos finitos que atingem o tamanho máximo sob a condição de que o número de cobertura seja pelo menos , generalizando dois resultados anteriores de Frankl para suficientemente grande.
Este artigo estende a teoria dos vieses de comprimentos de ganchos para partições -centrais, estabelecendo desigualdades específicas entre as contagens de ganchos de diferentes comprimentos nessas partições por meio de métodos combinatórios.
Este artigo apresenta novos resultados sobre subárvores induzidas totalmente folheadas em pavimentações de Penrose P2, demonstrando que elas são cataleiros com até seis peças adicionais e refutando a conjectura de que existe uma única cataleira bi-infinita nesse contexto.
Este artigo estabelece uma conexão entre certas funções quase perfeitamente não lineares (APN) 2-para-1 e conjuntos de diferença relativos, demonstrando que o conjunto imagem de tais funções constitui um conjunto de diferença relativa e, consequentemente, ligando-as a funções bent por meio de um resultado de Pott.
Este artigo investiga métodos de decomposição para quirotopos, generalizando as operações de soma convexa e côncava para obter uma estimativa assintótica precisa do número de triangulações do "double circle" utilizando uma equação funcional e o método do núcleo.
Este artigo estabelece limites de fase para a probabilidade de um conjunto aleatório de subconjuntos definir uma base de matroide, demonstra que tais estruturas são quase certamente matroides pavimentados esparsos quando a condição é satisfeita, e utiliza um algoritmo guloso para refinar as estimativas assintóticas do número de matroides, pavimentados e esparsos pavimentados, permitindo que o posto cresça lentamente com .
Este artigo aprimora os teoremas de interseção restrita de Alon-Babai-Suzuki ao estabelecer limites superiores refinados baseados em somas de sombreados não triviais e ao demonstrar que, no contexto modular com resíduos consecutivos, o limite clássico não é atingível, fornecendo uma resposta parcial negativa a uma questão aberta dos autores originais.
Este artigo introduz a classe de grafos Bipartite-Almost Bipartite (BAB), que generaliza classes anteriores, descrevendo sua estrutura via decomposição de Gallai-Edmonds, obtendo expressões explícitas para seus núcleos e diademas, demonstrando a fatoração do determinante da matriz de adjacência em termos de seus componentes e confirmando uma conjectura sobre grafos R-disjuntos.